<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /*
      因为可以买卖k次
      dp[i][1]表示第一次持有股票的最大价值
      dp[i][2]表示第一次不持有股票的最大价值
      dp[i][3]表示第二次持有股票的最大价值
      因此有2k次

      当j为奇数时，表示当前持有股票 那么当天的最大价值为前面一天继续持有，或者前面一天不持有，当天买入
      dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i-1])
      当j为偶数时，表示当前不持有股票的最大价值。要么前一天也不持有，要么当天卖出
      */
      var maxProfit = function (k, prices) {
        let dp = new Array(prices.length + 1).fill().map(() => new Array(2 * k + 1).fill(0))
        for (let j = 1; j < 2 * k + 1; j += 2) {
          dp[0][j] = -prices[0]
        }
        for (let i = 1; i < dp.length; i++) {
          for (let j = 1; j < 2 * k + 1; j++) {
            if (j % 2 != 0) {
              dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i - 1])
            } else {
              dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i - 1])
            }
          }
        }
        return dp[dp.length - 1][2 * k]
      }
    </script>
  </body>
</html>
